//
//  CircularList.hpp
//  CircularList
//
//  Created by chenyh on 2021/2/4.
//

#ifndef CircularList_hpp
#define CircularList_hpp

#include <iostream>

template<typename DataType> class CircularList;

template<typename DataType>
class CircularListNode {
public:
    friend class CircularList<DataType>;
    CircularListNode()
    {
        m_next = NULL;
    }
    CircularListNode(DataType data,CircularListNode *nextOne = NULL)
    {
        m_data = data;
        m_next = nextOne;
    }
    ~CircularListNode()
    {
        m_next = NULL;
    }
private:
    CircularListNode *m_next; //指向下一个结点的指针
    DataType m_data;        //数据域
};
//循环链表定义
template<typename DataType> class CircularList {
public:
    CircularList()
    {
        head = new CircularListNode<DataType>();
        head->m_next = head;
        
    }
    
    ~CircularList()
    {
        cleanUp();
        delete head;
    }
    //清空循环链表；
    void cleanUp();
    //获取循环链表的长度
    int getLength();
    //查找具有value值的第i个元素，并返回其指针
    CircularListNode<DataType> * findNode(int i,DataType value);
    //在链表尾部插入元素
    bool insertNode(DataType data);
    //删除具有value值的所有元素
    bool deleteNode(DataType value);
    //获取指定元素的值
    DataType getValue(CircularListNode<DataType> *node);
private:
    CircularListNode<DataType> *head;
};

//
template <typename DataType>
void CircularList<DataType>:: cleanUp()
{
    CircularListNode<DataType> *p; //设置指示删除结点的指针
    while (head->m_next != head) {
        p=head->m_next; //初始化指示指针
        head->m_next = p->m_next; //将头指针指向下一个结点的下一个结点
        delete p;   //回收空间
    }
}

//
template <typename DataType>
int CircularList<DataType>:: getLength()
{
    int length = 0;
    CircularListNode<DataType> *p = head; //设置游标指针
    while (p->m_next != head) { //游走指针，直至指向头指针时结束
        p=p->m_next;
        length++;
    }
    return length;
}

template <typename DataType>
CircularListNode<DataType> * CircularList<DataType>:: findNode(int i, DataType value)
{
    int count = 0;
    CircularListNode<DataType> *p = head;
    while (count != i) {
        //遍历链表，寻找值与value相等的结点
        p=p->m_next;
        if (p->m_data == value) {
            count++;    //记录这是第几个符合条件的结点
        }
        if (p==head) {
            return NULL;    //链表中没有满足条件的结点
        }
    }
    
    return p;
}

template <typename DataType>
bool CircularList<DataType>:: insertNode(DataType data)
{
    CircularListNode<DataType> *p = head;
    //建立新结点
    CircularListNode<DataType> *node = CircularListNode<DataType>(data,NULL);
    if (node == NULL) { //新结点空间分配失败
        return false;
    }
    //寻找尾结点
    while (p->m_next != head) {
        p=p->m_next;
    }
    node->m_next = p->m_next;//插入新结点
    p->m_next = node;
    return true;
}
template <typename DataType>
bool CircularList<DataType>:: deleteNode(DataType value)
{
    int count = 0;    //删除的结点数
    CircularListNode<DataType> *p = head->m_next,*l=head;
    //便利链表
    while (p != head) {
        if (p->m_data == value) { //如果结点值与value相等,删除该结点并计数
            l->m_next = p->m_data;
            delete p;
            count ++;
            p=l->m_next;
        }else
        {
            l=p;    //结点不符合条件，直接移动指针
            p=p->m_next;
        }
    }
    if (count == 0) {
        return false;  //如果删除结点数为0，说明没有符合条件的结点
    }else
        return true;

}
template <typename DataType>
DataType CircularList<DataType>:: getValue(CircularListNode<DataType> *node)
{
    return node->m_data;
}

#endif /* CircularList_hpp */
